Solution: Regions Cut by Slashes

Let's solve the Regions Cut By Slashes problem using the Union Find pattern.

Statement#

An n×nn \times n grid is composed of nn, 1×11 \times 1 squares, where each 1×11 \times 1 square consists of a “/”, “\”, or a blank space. These characters divide the square into adjacent regions.

Given the grid represented as a string array, return the number of regions.

Note:

  1. Backslash characters are escaped, so “\” is represented as “\\”.
  2. A 1×11 \times 1 square in the grid will be referred to as a box.

Constraints:

  • The grid consists of only “/”, “\”, or " " characters.
  • 1 \leq grid.length \leq 30

The following demonstration shows how the grid can be visualized:

svg viewer

1 of 16

svg viewer

2 of 16

svg viewer

3 of 16

svg viewer

4 of 16

svg viewer

5 of 16

svg viewer

6 of 16

svg viewer

7 of 16

svg viewer

8 of 16

svg viewer

9 of 16

svg viewer

10 of 16

svg viewer

11 of 16

svg viewer

12 of 16

svg viewer

13 of 16

svg viewer

14 of 16

svg viewer

15 of 16

svg viewer

16 of 16

Solution#

The idea is to divide each 1×11 \times 1 box in the grid into four regions representing its north, west, east, and south regions. At the start, an n×nn \times n grid will contain (4×n×n)(4 \times n \times n) regions. We will gradually reduce the number of regions by merging the regions inside each box based on the character they contain and then connecting them with their neighboring boxes. This merging and connecting will be done using the union find algorithm. In the union find algorithm, the union by rank and path compression optimizations will be applied. In the end, the number of connected components will represent the correct number of regions inside the grid.

Here’s how the algorithm works:

  • We create a parent array containing 4×n×n4 \times n \times n elements where each element equals its corresponding index.

    • Every four consecutive elements in this array represent a 1×11\times1 box in the grid.

    • We associate each 1×11\times1 grid square with four nodes—north, west, east, and south—representing four triangles inside the square. That’s how every one of these four elements inside the parent list represents the north, west, east, and south components of the box, respectively.

    • Each element in the array is initially equal to its respective index. For example:

      • The grid[0][0] box will comprise of the elements: 0, 1, 2, and 3.

      • The grid[0][1] box will comprise of the elements: 4, 5, 6, and 7, and so on.

  • Next, we traverse each character of the grid array:

  • We use the union method to merge the regions within each box depending on the character it contains:

    • If the box contains a “/” character, it will be partitioned into two regions. Therefore, we will merge the north-west and east-south regions to convert the box into two connected components.

    • If the box contains a “\\” character, it will be partitioned into two regions. Therefore, we will merge the north-east and west-south regions to convert the box into two connected components.

    • If the box contains a " " character, it will be converted to a single region. Therefore, we combine all four regions of the box to convert the box into a single connected component.

The illustration below shows how the regions within a box are merged:

svg viewer

1 of 3

svg viewer

2 of 3

svg viewer

3 of 3

  • Next, we connect the current box with the neighboring boxes on it’s top, bottom, left, and right:

    • The north region of the current box connects with the south region of the box above it.

    • The south region of the current box connects with the north region of the box below it.

    • The west region of the current box connects with the east region of the box to its left.

    • The east region of the current box connects with the west region of the box to its right.

  • After the grid array has been traversed completely, the number of connected components in parent array are equal to the correct number of regions in the grid. So, we will traverse the parent array to find the number of connected components:

    • We maintain a variable, count, initialized to 0 to count the number of connected components.

    • For each element, parents[i], we will use the find(parents[i]) method to check if the current node is a parent of itself, i.e. the current element parents[i] is equal to its respective index, i:

      • If it is, we have found a connected component and increment the count variable.

      • Otherwise, we move forward.

  • After the parent array has been traversed completely, we return count as it contains the number of regions in the grid.

The slides below illustrate how the algorithm runs:

svg viewer

1 of 40

svg viewer

2 of 40

svg viewer

3 of 40

svg viewer

4 of 40

svg viewer

5 of 40

svg viewer

6 of 40

svg viewer

7 of 40

svg viewer

8 of 40

svg viewer

9 of 40

svg viewer

10 of 40

svg viewer

11 of 40

svg viewer

12 of 40

svg viewer

13 of 40

svg viewer

14 of 40

svg viewer

15 of 40

svg viewer

16 of 40

svg viewer

17 of 40

svg viewer

18 of 40

svg viewer

19 of 40

svg viewer

20 of 40

svg viewer

21 of 40

svg viewer

22 of 40

svg viewer

23 of 40

svg viewer

24 of 40

svg viewer

25 of 40

svg viewer

26 of 40

svg viewer

27 of 40

svg viewer

28 of 40

svg viewer

29 of 40

svg viewer

30 of 40

svg viewer

31 of 40

svg viewer

32 of 40

svg viewer

33 of 40

svg viewer

34 of 40

svg viewer

35 of 40

svg viewer

36 of 40

svg viewer

37 of 40

svg viewer

38 of 40

svg viewer

39 of 40

svg viewer

40 of 40

Let’s take a look at the code for this solution below:

main.py
union_find.py
Regions Cut by Slashes

Time complexity#

The time complexity of this solution is O(n2)O(n^2), (where nn is the length of the grid) and can be calculated as:

  • The nested loops iterate over each character in the grid, resulting in O(n2)O(n^2) iterations.

  • The time complexity of the the union and find functions is O(αn)O( \alpha n) as both path compression and union find by rank are being used. αn\alpha n is almost constant time and grows very slowly with the input size, so the time complexity of both these functions can be considered as constant time for practical purposes.

  • The loop to find the number of connected components traverses the parent array once, resulting in O(4×n×n)O(4 \times n \times n) iterations.

Therefore, the overall time complexity becomes O(n2×αn+(4×n×n))O(n^2 \times \alpha n + (4\times n \times n)), which simplifies to O(n2)O(n^2).

Space Complexity#

The space complexity of this solution is O(n2)O(n^2) and can be calculated as:

  • Space occupied by the parent array: O(4×n×n)O(4 \times n \times n).

  • Space occupied by the rank array: O(4×n×n)O(4 \times n \times n).

Therefore, the overall time complexity is O(2(4×n×n))O(2(4\times n \times n)), which simplifies to O(n2)O(n^2).

Regions Cut by Slashes

Accounts Merge